package code.commonAlgorithm;

import java.util.Arrays;

/**
 * @author cuihaoran
 * @date 2024/11/29
 */
public class HeapSort {

    static public void heapSort(int[] nums) {
        int len = nums.length;
        buildHeap(nums);
        for (int i = len - 1; i >= 0; i--) {
            swap(nums, i, 0);
            heapifyDown(nums, i, 0);
        }
    }

    private static void buildHeap(int[] nums) {
        int len = nums.length;
        int lastParent = (len - 2) / 2;
        for (int i = lastParent; i >= 0; i--) {
            heapifyDown(nums, len, i);
        }
    }

    /**
     * 下沉操作：排序时用到
     * @param nums
     * @param len
     * @param i
     */
    private static void heapifyDown(int[] nums, int len, int i) {
        int c1 = i * 2 + 1;
        int c2 = i * 2 + 2;
        int max = i;
        if (c1 < len && nums[c1] > nums[max])
            max = c1;
        if (c2 < len && nums[c2] > nums[max])
            max = c2;
        if (max != i) {
            swap(nums, i, max);
            heapifyDown(nums, len, max);
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        int[] a = new int[]{3,5,7,21,4,6,2};
        HeapSort.heapSort(a);
        System.out.println(Arrays.toString(a));
    }
}
